#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : GrayCode.py
# @Time    : 2020/9/3 10:08
# @Description:
from typing import List


class Solution:
    def grayCode(self, n: int) -> List[int]:
        """
        The gray code is a binary numeral system where two successive values differ in only one bit.

        Given a non-negative integer n representing the total number of bits in the code, print the sequence of
        gray code. A gray code sequence must begin with 0.

        Example 1:
            Input: 2
            Output: [0,1,3,2]
            Explanation:
                00 - 0
                01 - 1
                11 - 3
                10 - 2
            For a given n, a gray code sequence may not be uniquely defined.
            For example, [0,2,3,1] is also a valid gray code sequence.
                00 - 0
                10 - 2
                11 - 3
                01 - 1
        Example 2:
            Input: 0
            Output: [0]
            Explanation: We define the gray code sequence to begin with 0.
                         A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
                         Therefore, for n = 0 the gray code sequence is [0].

        :param n:
        :return:
        """
        res, head = [0], 1
        for i in range(n):
            for j in range(len(res) - 1, -1, -1):
                res.append(head + res[j])
            head <<= 1
        return res


if __name__ == '__main__':
    S = Solution()
    n = 3
    # n = 2
    print(S.grayCode(n))
    print('done')
